home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / standards / sgml / nist / parse2b / dettrav.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-09-13  |  12.1 KB  |  292 lines
  1. /* National Institute of Standards and Technology (NIST)
  2. /* National Computer System Laboratory (NCSL)
  3. /* Office Systems Engineering (OSE) Group
  4. /* ********************************************************************
  5. /*                            D I S C L A I M E R
  6. /*                              (March 8, 1989)
  7. /*  
  8. /* There is no warranty for the NIST NCSL OSE SGML parser and/or the NIST
  9. /* NCSL OSE SGML parser validation suite.  If the SGML parser and/or
  10. /* validation suite is modified by someone else and passed on, NIST wants
  11. /* the parser's recipients to know that what they have is not what NIST
  12. /* distributed, so that any problems introduced by others will not
  13. /* reflect on our reputation.
  14. /* 
  15. /* Policies
  16. /* 
  17. /* 1. Anyone may copy and distribute verbatim copies of the SGML source
  18. /* code as received in any medium.
  19. /* 
  20. /* 2. Anyone may modify your copy or copies of SGML parser source code or
  21. /* any portion of it, and copy and distribute such modifications provided
  22. /* that all modifications are clearly associated with the entity that
  23. /* performs the modifications.
  24. /* 
  25. /* NO WARRANTY
  26. /* ===========
  27. /* 
  28. /* NIST PROVIDES ABSOLUTELY NO WARRANTY.  THE SGML PARSER AND VALIDATION
  29. /* SUITE ARE PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER
  30. /* EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  31. /* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  32. /* THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS
  33. /* WITH YOU.  SHOULD THE SGML PARSER OR VALIDATION SUITE PROVE DEFECTIVE,
  34. /* YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.
  35. /* 
  36. /* IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW WILL NIST BE LIABLE FOR
  37. /* DAMAGES, INCLUDING ANY LOST PROFITS, LOST MONIES, OR OTHER SPECIAL,
  38. /* INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR
  39. /* INABILITY TO USE (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA
  40. /* BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY THIRD PARTIES OR A
  41. /* FAILURE OF THE PROGRAM TO OPERATE WITH PROGRAMS NOT DISTRIBUTED BY
  42. /* NIST) THE PROGRAM, EVEN IF YOU HAVE BEEN ADVISED OF THE POSSIBILITY OF
  43. /* SUCH DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY.
  44. */
  45.  
  46. /************************************************************************/
  47. /*   TITLE:          SGML PARSER                                        */
  48. /*   SYSTEM:         DTD PROCESSOR                                      */
  49. /*   SUBSYSTEM:                                                         */
  50. /*   SOURCE FILE:    DETTRAV.C                                          */
  51. /*   AUTHOR:         Michael Garris                                     */
  52. /*                                                                      */
  53. /*   DATE CREATED:                                                      */
  54. /*   LAST MODIFIED:                                                     */
  55. /*                                                                      */
  56. /*                  REVISIONS                                           */
  57. /*   WHEN      WHO            WHY                                       */
  58. /************************************************************************/
  59. #include <stdio.h>
  60. #include "detdefs.h"
  61. #include "detglbl.h"
  62.  
  63. /************************************************************************/
  64. /************************************************************************/
  65. /* PROCINORDR is a traversal which visits every state in an FSA starting*/
  66. /* at the start state "startstate".                                     */
  67. /************************************************************************/
  68. void procinordr(startstate,finalstate)
  69. STATE *startstate,*finalstate;
  70. {
  71.    STATE *node;/* current state being visited */
  72.  
  73.    /* set current node to "startstate" */
  74.    node = startstate;
  75.    /* if the finalstate has not be reached ... */
  76.    if(startstate != finalstate){
  77.       /* if the current state's left pointer is not NULL, not point*/
  78.       /* back, and not looping directly back to itself ... */
  79.       if((node->lptr != NULL) && (node->llabel != BACK)
  80.           && (node != node->lptr)){
  81.          /* continue to traverse left */
  82.          procinordr(node->lptr,finalstate);
  83.       }
  84.       /* the current node's left pointer is either NULL, pointing */
  85.       /* back, or pointing directly to itself, so invoke "procnode" */
  86.       procnode(node);
  87.       /* now look right */
  88.       /* if current node's right pointer is not NULL, not pointing */
  89.       /* back, and not looping directly back to itself ... */
  90.       if((node->rptr != NULL) && (node->rlabel != BACK)
  91.           && (node != node->rptr)){
  92.          /* continue to traverse right */
  93.          procinordr(node->rptr,finalstate);
  94.       }
  95.    }
  96.    /* otherwise final state has been found */
  97.    else{
  98.       /* process the final state */
  99.       procnode(startstate);
  100.    }
  101. }
  102. /************************************************************************/
  103. /************************************************************************/
  104. /* PROCNODE takes a state structure and prints out the state's address, */
  105. /* the state's left pointer address and label, and the state's right    */
  106. /* pointer address and label.                                           */
  107. /************************************************************************/
  108. void procnode(node)
  109. STATE *node;
  110. {
  111. #ifdef DEBUG
  112.    printf("for node at address %04x\n", node);
  113.    printf("  lptr = %04x, llabel = %04x, linst = %d\n", 
  114.        node->lptr, node->llabel, node->linst);
  115.    printf("  rptr = %04x, rlabel = %04x, rinst = %d\n", 
  116.        node->rptr, node->rlabel, node->rinst);
  117.    printf("___________________________________\n");
  118. #else
  119.    return;
  120. #endif
  121. }
  122. /************************************************************************/
  123. /************************************************************************/
  124. /* PROCDET is a traversal which visits every state in an FSA starting   */
  125. /* at the start state "startstate", and for each state visited, it calls*/
  126. /* a procedure to check the current state passed for "ambiguity".       */
  127. /************************************************************************/
  128. void procdet(startstate,finalstate)
  129. STATE *startstate,*finalstate;
  130. {
  131.    register STATE *node;/* current state being looked at */
  132.    STATE *currnode[BUFFSIZE];/* list to hold all states visited */
  133.    /* while a state is tested for ambiguity */
  134.    int nodeindex = 0;/* subscript to "currnode" */
  135.    int toklist[BUFFSIZE];/* list to hold all edges labeled with */
  136.    /* tokens and their associated instance code*/
  137.    int *tokindex = toklist;/* pointer to toklist initialized to the */
  138.    /* beginning of toklist */
  139.    int *tokmax = tokindex + BUFFSIZE - 2;
  140.    register int i;
  141.    memset((char *)toklist, 0, BUFFSIZE);
  142.    /* set current state to state that was passed */
  143.    node = startstate;
  144.    /* if the state passed is not the finalstate ...*/
  145.    if(startstate != finalstate){
  146.       /* if the left pointer of the current state is not NULL, not */
  147.       /* pointing back, and not looping directly to itself ... */
  148.       if((node->lptr != NULL) && (node->llabel != BACK)
  149.           && (node != node->lptr)){
  150.          /* continue to traverse left */
  151.          procdet(node->lptr,finalstate);
  152.       }
  153.       /* otherwise send the current state and a state list to a */
  154.       /* procedure to detect any ambiguity from that state */
  155.       findlabels(node,currnode,&nodeindex,toklist,&tokindex,tokmax);
  156.       /* if the right pointer of the current state is not NULL, not */
  157.       /* pointing back, and not looping directly to itself ...*/
  158.       if((node->rptr != NULL) && (node->rlabel != BACK)
  159.           && (node != node->rptr)){
  160.          /* continue to traverse right */
  161.          procdet(node->rptr,finalstate);
  162.       }
  163.    }
  164.    /* otherwise the current state is the final state */
  165.    else{
  166.       /* invoke procedure to determine ambiguity on the final state */
  167.       findlabels(startstate,currnode,&nodeindex,toklist,&tokindex,tokmax);
  168.    }
  169. }
  170. /************************************************************************/
  171. /************************************************************************/
  172. /* FINDLABELS takes a state from an FSA and traverses all unique paths  */
  173. /* from that state recording each first occurance of a non-NULL edge    */
  174. /* on each unique path.  On completing each unique path, this procedure */
  175. /* searches a list of the non-NUll edges seen and determines is the     */
  176. /* state is "ambiguous" according to the definition stated by SGML.     */
  177. /************************************************************************/
  178. void findlabels(node,currnode,nodeindex,toklist,ptrin,tokmax)
  179. register STATE *node;
  180. STATE *currnode[];
  181. int *toklist,**ptrin;
  182. int *nodeindex;
  183. int *tokmax;
  184. {
  185.    int *tokindex = *ptrin;
  186.  
  187.    /* put the current state's address into the list of states visited */
  188.    if (*nodeindex >= BUFFSIZE) {
  189.       printf("overflow in findlabels\n");
  190.       exit(0);
  191.    }
  192.    currnode[(*nodeindex)] = node;
  193.    /* increment the subscript at the location nodeindex */
  194.    *nodeindex = *nodeindex + 1;
  195.    /* if the current state's left edge is labelled EMPTY or BACK, and */
  196.    /* the current state's left edge is not pointing to a state already*/
  197.    /* visited by this traversal on the state passed by procdet ...    */
  198.    if(node->llabel < 0){
  199.       register int i;
  200.       register STATE **jcurrnode = currnode;
  201.       register STATE *jnode = node->lptr;
  202.       for (i = 0; i < *nodeindex; i++) {
  203.          if (*jcurrnode++ == jnode)
  204.             goto OUT1;
  205.       }
  206.       /* continue to traverse left on a unique path */
  207.       findlabels(node->lptr,currnode,nodeindex,toklist,&tokindex, tokmax);
  208.    }
  209. OUT1:
  210.    /* if the current state is not pointing left to a NULL, EMPTY, and */
  211.    /* BACK ...*/
  212.    if((node->lptr != NULL) && (node->llabel != EMPTY)
  213.        && (node->llabel != BACK)){
  214.       /* then the edge is labelled with a token, so print it out */
  215.       if(searchamb(node->llabel,node->linst,toklist,tokindex))
  216.          ambmodel = TRUE;
  217.       if((tokindex + 2) >= tokmax) {
  218.          printf("tokindex overflow in findlabels()\n");
  219.          exit(0);
  220.       }
  221.       *tokindex++ = node->llabel;
  222.       *tokindex++ = node->linst;
  223.    }
  224.  
  225.    /* if the current state's right edge is labelled EMPTY or BACK, and */
  226.    /* the current state's right edge is not pointing to a state already*/
  227.    /* visited by this traversal on the state passed by procdet ...     */
  228.    if(node->rlabel < 0){
  229.       register int i;
  230.       register STATE **jcurrnode = currnode;
  231.       register STATE *jnode = node->rptr;
  232.       for (i = 0; i < *nodeindex; i++) {
  233.          if (*jcurrnode++ == jnode)
  234.             goto OUT2;
  235.       }
  236.       findlabels(node->rptr,currnode,nodeindex,toklist,&tokindex,tokmax);
  237.    }
  238. OUT2:
  239.    /* otherwise the edge is labelled by a token */
  240.    if((node->rptr != NULL) && (node->rlabel != EMPTY)
  241.        && (node->rlabel != BACK)){
  242.       /* print the labelled edge out */
  243.       if(searchamb(node->rlabel,node->rinst,toklist,tokindex))
  244.          ambmodel = TRUE;
  245.       if((tokindex + 2) >= tokmax) {
  246.          printf("tokindex overflow in findlabels()\n");
  247.          exit(0);
  248.       }
  249.       *tokindex++ = node->rlabel;
  250.       *tokindex++ = node->rinst;
  251.    }
  252.    *ptrin = tokindex;
  253. }
  254. /************************************************************************/
  255. /************************************************************************/
  256. /* SEARCHAMB*/
  257. /************************************************************************/
  258. int searchamb(label,inst,toklist,tokindex)
  259. int label,inst,*toklist,*tokindex;
  260. {
  261.    int i;
  262.    register int *ptr = toklist;
  263.  
  264.    while(ptr != tokindex){
  265.       if(label == *ptr++){
  266.          if(inst != *ptr++)
  267.             return(TRUE);
  268.       }
  269.       else
  270.          ++ptr;
  271.    }
  272.    return(FALSE);
  273. }
  274. /************************************************************************/
  275. /************************************************************************/
  276. /* SSEARCH searches a list of states for a match on the current state    */
  277. /* "node".  If a match occurs then the function returns FALSE, otherwise*/
  278. /* the function returns TRUE.                                           */
  279. int ssearch(node,currnode,nodeindex)
  280. STATE *node,*currnode[];
  281. register int nodeindex;
  282. {
  283.    register int i,k = 0;
  284.  
  285.    for(i = 0; i < nodeindex; ++i){
  286.       if(currnode[k++] == node)
  287.          return(FALSE);
  288.    }
  289.    return(TRUE);
  290. }
  291. /************************************************************************/
  292.